package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-07-08 15:01
 */
public class 题库_0212_单词搜索II {

  public static void main(String[] args) {
    char[][] board = {
        {'a', 'b', 'c'},
        {'a', 'e', 'd'},
        {'a', 'f', 'g'}
    };

    String[] words = { "eaabcdgfa" };

    Solution solution = new Solution();

    System.out.println(solution.findWords(board, words));

  }


  static
  class Solution {

    private final int[][] nexts = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<String> findWords(char[][] board, String[] words) {
      List<String> answer = new ArrayList<>();

      for (String word : words) {
        if (isExists(board, word)) {
          answer.add(word);
        }
      }

      return answer;
    }

    private boolean isExists(char[][] board, String word) {
      for (int i = 0; i < board.length; ++i) {
        for (int j = 0; j < board[0].length; ++j) {
          if (isExists(board, i, j, new boolean[board.length][board[0].length], word, 0)) {
            return true;
          }
        }
      }
      return false;
    }

    private boolean isExists(char[][] board, int i, int j, boolean[][] visited, String word, int index) {
      if (index == word.length()) {
        return true;
      }
      if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) {
        return false;
      }
      visited[i][j] = true;
      for (int[] next : nexts) {
        if (isExists(board, i + next[0], j + next[1], visited, word, index + 1)) {
          return true;
        }
      }
      visited[i][j] = false;

      return false;
    }

  }

}
